package leetcode_day._2021._202104._2131;

import java.util.HashMap;
import java.util.Map;

/**
 * @author yzh
 * @version 1.0
 * @date 2021/4/29 20:03
 * 青蛙过河
 * 回溯
 * cur: 当前走到的索引
 * k: 上一次走的步数
 */
public class _29_403 {
    private Map<Integer, Integer> map = new HashMap<>();
    private Map<String, Boolean> cache = new HashMap<>();
    public boolean canCross(int[] stones) {
        for (int i = 0; i < stones.length; i++) map.put(stones[i], i);
        if (!map.containsKey(1)) return false;
        return dfs(stones, 1, 1);
    }
    public boolean dfs(int[] stones, int cur, int k) {
        if (!cache.getOrDefault(stones[cur] + "_" + k, true)) return false;
        if (cur == stones.length - 1) return true;
        for (int i = -1; i <= 1; i++) {
            if (0 == k + i) continue;
            if (map.containsKey(stones[cur] + k + i)) {
                boolean flag = dfs(stones, map.get(stones[cur] + k + i), k + i);
                cache.put(stones[cur] + "_" + k, flag);
                if (flag) return flag;
            }
        }
        return false;
    }
}
